Leetcode55——Jump Game

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Jump Game

2. Solution

  • 递归遍历所有的可能
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
bool canJump(vector<int>& nums) {
return jump(nums, 0);
}

bool jump(vector<int>& nums, int start) {
if(start + nums[start] >= nums.size() - 1) {
return true;
}
for(int i = 1; i <= nums[start]; i++) {
if(nums[start + i] != 0) {
if(jump(nums, start + i)) {
return true;
}
else {
nums[start + i] = 0;
}
}
}
nums[start] = 0;
return false;
}
};
  • 贪心算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
bool canJump(vector<int>& nums) {
int current = nums.size() - 1;
for(int i = current - 1; i >= 0; i--) {
if(nums[i] + i >= current) {
current = i;
}
}
if(current == 0) {
return true;
}
else {
return false;
}
}
};

Reference

  1. https://leetcode.com/problems/jump-game/description/
如果有收获,可以请我喝杯咖啡!